/**
题目:
    数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
    示例：
    输入：n = 3
    输出：[
        "((()))",
        "(()())",
        "(())()",
        "()(())",
        "()()()"
        ]
    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/generate-parentheses
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路:
    递归
*/
class Solution {
public:
   //dfs
   vector<string> res;
    vector<string> generateParenthesis(int n) {
        gen( "", n , n);
        return res;
    }
    void gen(string path,int left,int right){
        if(left==0&&right==0){
            res.push_back(path);
            return ;
        }
        if(left>0){
            gen( path+"(", left-1, right);
        }
        //这里很重要，什么时候才能放右括号呢？是左括号还没为0的时候
        if(left<right){
            gen( path+")", left , right-1);
        }    
    }
};